home *** CD-ROM | disk | FTP | other *** search
/ C++ für Kids / C++ for kids.iso / SETUP / CBUILDER / DATA.Z / ALG3.CPP < prev    next >
Encoding:
C/C++ Source or Header  |  1997-02-20  |  6.5 KB  |  225 lines
  1. /**************************************************************************
  2.  *
  3.  * alg3.cpp - Sample programs for STL generic algorihtms that modify
  4.  *   their arguments in place.  Section 12.4
  5.  *
  6.  * $Id: alg3.cpp,v 1.4 1995/08/29 18:43:04 oberg Exp $
  7.  *
  8.  * $$RW_INSERT_HEADER "slyrs.cpp"
  9.  *
  10.  **************************************************************************/
  11.  
  12. # include <iostream.h>
  13. # include <vector>
  14. # include <list>
  15. # include <algorithm>
  16.  
  17. # include <ctype.h>
  18. # include <string>
  19. # include <string.h>
  20. using namespace std;
  21.  
  22. class iotaGenerator {
  23. public:
  24.     iotaGenerator (int iv) : current(iv) { }
  25.     operator () () { return current++; }
  26. private:
  27.     int current;
  28. };
  29.  
  30. bool isEven(int n) { return 0 == (n % 2); }
  31.  
  32. void reverse_example ()
  33.     // illustrate the use of the reverse function
  34. {
  35.     cout << "Illustrate reverse algorithm" << endl;
  36.     
  37.         // example 1, reversing a string
  38.     char * text = "Rats live on no evil star";
  39.     reverse (text, text + strlen(text));
  40.     cout << text << endl;
  41.     
  42.         // example 2, reversing a list
  43.     list<int> iList;
  44.     generate_n(inserter(iList, iList.begin()), 10, iotaGenerator(2));
  45.     reverse (iList.begin(), iList.end());
  46.     copy (iList.begin(), iList.end(),
  47.             ostream_iterator<int>(cout, " ")), cout << endl;    
  48. }
  49.  
  50. void replace_example ()
  51.     // illustrate the use of the replace function
  52. {
  53.     cout << "Illustrate replace algorithm" << endl;
  54.     
  55.         // make vector 0 1 2 3 4
  56.     vector<int> numbers(11);    
  57.     for (int i = 0; i < 11; i++)
  58.         numbers[i] = i < 5 ? i : 10 - i;
  59.     copy (numbers.begin(), numbers.end(),
  60.         ostream_iterator<int> (cout, " ")), cout << endl;
  61.  
  62.         
  63.         // replace 0 by 2
  64.     replace (numbers.begin(), numbers.end(), 3, 7);
  65.     copy (numbers.begin(), numbers.end(),
  66.         ostream_iterator<int> (cout, " ")), cout << endl;
  67.         
  68.         // replace even numbers by 9
  69.     replace_if (numbers.begin(), numbers.end(), isEven, 9);
  70.     copy (numbers.begin(), numbers.end(),
  71.         ostream_iterator<int> (cout, " ")), cout << endl;
  72.         
  73.         // copy into a list, replacing 9 by 3
  74.     int aList[] = {2, 1, 4, 3, 2, 5};
  75.     int bList[6];
  76.     int cList[6];
  77.     replace_copy (aList, aList+6, &bList[0], 2, 7);
  78.     replace_copy_if (bList, bList+6, &cList[0], bind2nd(greater<int>(), 3), 8);
  79.     copy (bList, bList + 6, ostream_iterator<int> (cout, " ")), cout << endl;
  80.     copy (cList, cList + 6, ostream_iterator<int> (cout, " ")), cout << endl;
  81. }
  82.  
  83. void rotate_example ()
  84.     // illustrate the use of the rotate function
  85. {
  86.     cout << "Illustrate rotate algorithm" << endl;
  87.     
  88.         // create the list 1 2 3 ... 10
  89.     list<int> iList;
  90.     generate_n(inserter(iList, iList.begin()), 10, iotaGenerator(1));
  91.         
  92.         // find the location of the seven
  93.     list<int>::iterator  middle = find(iList.begin(), iList.end(), 7);
  94.     
  95.         // now rotate around that location
  96.     rotate(iList.begin(), middle, iList.end());
  97.     copy (iList.begin(), iList.end(),
  98.         ostream_iterator<int>(cout, " ")), cout << endl;
  99.         
  100.         // rotate again around the same location
  101.     list<int> cList;
  102.     rotate_copy(iList.begin(), middle, iList.end(),
  103.         inserter(cList, cList.begin()));
  104.     copy (cList.begin(), cList.end(),
  105.         ostream_iterator<int>(cout, " ")), cout << endl;
  106. }
  107.  
  108.  
  109. void partition_example ()
  110.     // illustrate the use of the paration function
  111. {
  112.     cout << "Illustrate partition algorithm" << endl;
  113.     
  114.         // first make the vector 1 2 3 ... 10
  115.     vector<int> numbers(10);
  116.     generate(numbers.begin(), numbers.end(), iotaGenerator(1));
  117.     
  118.         // now put the odd values low, even values high
  119.     vector<int>::iterator result = partition (numbers.begin(), numbers.end(), isEven);
  120.     copy (numbers.begin(), numbers.end(),
  121.         ostream_iterator<int>(cout, " ")), cout << endl;
  122.     cout << "middle location " << result - numbers.begin() << endl;    
  123.     
  124.         // now do a stable partition
  125.     generate(numbers.begin(), numbers.end(), iotaGenerator(1));
  126.     //stable_partition(numbers.begin(), numbers.end(), isEven);
  127.     copy (numbers.begin(), numbers.end(),
  128.         ostream_iterator<int>(cout, " ")), cout << endl;
  129. }
  130.  
  131.  
  132. bool nameCompare(char * a, char * b) { return strcmp(a, b) <= 0; }
  133.  
  134. void permutation_example ()
  135.     // illustrate the use of the next_permutation function
  136. {
  137.         // start with the values 1 2 3 in sequence
  138.     int start [] = {1, 2, 3 };
  139.     
  140.     do
  141.         copy (start, start + 3, ostream_iterator<int> (cout, " ")), cout << endl;
  142.     while (next_permutation(start, start + 3));
  143.         
  144.     char * names[] = {"Alpha", "Beta", "Gamma"};
  145.     do
  146.         copy (names, names + 3, ostream_iterator<char *> (cout, " ")), cout << endl;
  147.     while (next_permutation(names, names + 3, nameCompare));
  148.     
  149.     char * word = "bela";
  150.     do
  151.         cout << word << ' ';
  152.     while (prev_permutation(word, &word[4]));
  153.     cout << endl;    
  154. }
  155.  
  156. void inplace_merge_example ()
  157.     // illustrate the use of the inplace_merge function
  158. {
  159.     cout << "Illustrate inplace merge algorithm" << endl;
  160.     
  161.         // first generate the numbers 0 2 4 6 8 1 3 5 7 9
  162.     vector<int> numbers(10);
  163.     for (int i = 0; i < 10; i++)
  164.         numbers[i] = i < 5 ? 2 * i : 2 * (i - 5) + 1;
  165.     copy (numbers.begin(), numbers.end(),
  166.         ostream_iterator<int> (cout, " ")), cout << endl;
  167.     vector<int>::iterator midvec = find(numbers.begin(), numbers.end(), 1);
  168.     
  169.         // copy them into a list
  170.     list<int> numList;
  171.     copy(numbers.begin(), numbers.end(),
  172.             inserter(numList, numList.begin()));
  173.     list<int>::iterator midList = find(numList.begin(), numList.end(), 1);
  174.     copy (numList.begin(), numList.end(),
  175.         ostream_iterator<int> (cout, " ")), cout << endl;
  176.  
  177.         // now put them back together
  178.     inplace_merge(numbers.begin(), midvec, numbers.end());
  179.     inplace_merge(numList.begin(), midList, numList.end());
  180.     copy (numList.begin(), numList.end(),
  181.         ostream_iterator<int> (cout, " ")), cout << endl;
  182. }
  183.  
  184. struct RandomInteger
  185. {
  186.     operator() (int m) { return rand() % m; }
  187. };
  188.  
  189. void random_shuffle_example()
  190.     // illustrate the use of the random_shuffle function
  191. {
  192.         // first make the vector 1 2 3 ... 10
  193.     vector<int> numbers(10);
  194.     generate(numbers.begin(), numbers.end(), iotaGenerator(1));
  195.  
  196.     RandomInteger random;
  197.     
  198.         // randomly shuffle the elements
  199.     random_shuffle(numbers.begin(), numbers.end(), random);
  200.     copy (numbers.begin(), numbers.end(),
  201.         ostream_iterator<int>(cout, " ")), cout << endl;
  202.             
  203.         // do it again
  204.     random_shuffle(numbers.begin(), numbers.end(), random);
  205.     copy (numbers.begin(), numbers.end(),
  206.         ostream_iterator<int>(cout, " ")), cout << endl;
  207. }
  208.  
  209. int main()
  210. {
  211.     cout << "STL generic algorithms -- in-place algorithms" << endl;
  212.  
  213.     reverse_example();
  214.     replace_example();
  215.     rotate_example();
  216.     partition_example();
  217.     permutation_example();
  218.     inplace_merge_example();
  219.     random_shuffle_example();
  220.     
  221.     cout << "End of in-place algorithm sample program"  << endl;
  222.  
  223.     return 0;
  224. }
  225.